//
// Created by Lenovo on 2021/5/31.
//

#ifndef TSP_01BAG_H
#define TSP_01BAG_H
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN= 1e3+10;
int dp[MAXN];
int weight[MAXN]={79,58,86,11,28,62,15,68};
int val[MAXN]={83,14,54,79,72,52,48,62};
int flag[MAXN];
struct nodebag{
    int id;
    double worth;
    friend bool operator <(const nodebag& a,const nodebag& b){
        return a.worth>b.worth;
    }
}a[MAXN];
class Bag
{
public:
    void init(){
        int num = 20;
        for(int i = 0;i<num;i++) {
            val[i] = rand()%100;
            do{
                weight[i] = rand()%100;
            }while(weight[i]==0);
        }
    }
    int DP(int V){
        for(int i = 0;i<num;i++)
        {
            for(int j = V;j>weight[i];j--) dp[j] = max(dp[j],dp[j-weight[i]]+val[i]);
        }
        return dp[V];
    }
    int greedy(int V){
        //cout<<"******"<<endl;
        for(int i = 0;i<num;i++){
            //cout<<i<<endl;
            a[i].worth = (1.0*val[i])/(weight[i]*1.0);
            a[i].id = i;
        }
        //cout<<"*****"<<endl;
        sort(a,a+num);
        int ans = 0;
        for(int i = 0;i<num;i++){
            if(V-weight[a[i].id]>=0){
                V -= weight[a[i].id];
                ans += val[a[i].id];
            }
            else return ans;
        }
    }
private:
    int num = 8;
};
#endif //TSP_01BAG_H
